#ifndef MINHEAP_H_
#define MINHEAP_H_

#include<vector>
#include<iostream>
using std::vector;
using std::ostream;
enum Tag {L, R};

template<class T> class MinHeap;

template<class T>
ostream& operator<< (ostream & output, const MinHeap<T> & heap)
{
	int j = heap.data.size();
	for(int i=0; i<j; i++)
		output<<heap.data[i]<<" ";
	return output;
}

template<class T>
class MinHeap
{
private:
	vector<T> data;
	void Swap(int x, int y);
	void BuildHeap();
public:
	MinHeap(const int t_max_size);
	MinHeap(const vector<T> t_data);
	~MinHeap(){};
	bool IsLeaf(int pos) const;
	int Child(int pos, Tag t) const;
	int Parent(int pos) const;
	bool Remove(int pos, T & t_data);
	bool Insert(const T & t_data);
	bool RemoveMin(T & t_data);
	void SiftUp(int pos);
	void SiftDown(int left);
	friend ostream& operator<< <T>(ostream & output, const MinHeap<T> & heap);

};

template<class T>
MinHeap<T>::MinHeap(const int t_max_size)
{
	if(t_max_size<=0)
		return;
	data.size() = 0;
	data.resize(t_max_size);
	BuildHeap();
}
template<class T>
MinHeap<T>::MinHeap(const vector<T> t_data)
{
	data = t_data;
	BuildHeap();
}
template<class T>
bool MinHeap<T>::IsLeaf(int pos) const
{
	return(pos>=data.size()/2)&&(pos<data.size());
}
template<class T>
void MinHeap<T>::BuildHeap()
{
	int t_size = data.size();
	if(t_size)
		for(int i=t_size/2 - 1; i>=0; i--)
			SiftDown(i);
}
template<class T>
void MinHeap<T>::Swap(int x, int y)
{
	T temp = data[x];
	data[x] = data[y];
	data[y] = temp;
}
template<class T>
int MinHeap<T>::Child(int pos, Tag t) const
{
	if(t == L)
		return 2*pos + 1;
	else if(t == R)
		return 2*pos + 2;
}

template<class T>
int MinHeap<T>::Parent(int pos) const
{
	return (pos-1)/2;
}

template<class T>
bool MinHeap<T>::Insert(const T & t_data)
{
	if(data.size() == data.max_size())
		return false;
	data.push_back(t_data);
	SiftUp(data.size());
	return true;
}

template<class T>
bool MinHeap<T>::Remove(int pos, T & t_data)
{
	if((pos<0)||(pos>=data.size()))
		return false;
	T temp = data[pos];
	data[pos]=data[--data.size()];
	SiftUp(pos);
	SiftDown(pos);
	t_data = temp;
	return true;
}

template<class T>
bool MinHeap<T>::RemoveMin(T & t_data)
{
	if(data.empty())
		return false;
	else
	{
		Swap(0, --data.size());
		if(data.size()>1)
			SiftDown(0);
		return data[data.size()];
	}
}

template<class T>
void MinHeap<T>::SiftUp(int pos)
{
	int temp_pos = pos;
	T temp = data[temp_pos];
	while((temp_pos>0)&&(data[Parent(temp_pos)]>temp))
	{
		data[pos] = data[Parent(temp_pos)];
		temp_pos = Parent(temp_pos);
	}
	data[temp_pos] = temp;
}

template<class T>
void MinHeap<T>::SiftDown(int pos)
{
	int size = data.size();
	int t_parent = pos;
	int t_left = Child(pos, L);
	T temp = data[t_parent];
	while(t_left < size)
	{
		if((t_left<size-1)&&(data[t_left]>data[t_left+1]))
			t_left++;
		if(temp>data[t_left])
		{
			data[t_parent] = data[t_left];
			t_parent = t_left;
			t_left = Child(t_left, L);
		}
		else
			break;
	}
	data[t_parent] = temp;
}

#endif /* MINHEAP_H_ */
